package algo.A04_快速排序和归并排序;

import util.ArrayUtil;

/**
 * 三指针分区法
 * 类似于单向扫描法，但是增加一个相等指针指向等于基准的元素
 */
public class M03_快速排序_三指针分区法 {
    public static void main(String[] args) {
        int[] arr = ArrayUtil.getRandomArr(10, 1, 50);
        ArrayUtil.print(arr);
        quickSort(arr, 0, arr.length - 1);
        ArrayUtil.print(arr);
    }

    /**
     * 快速排序
     * @param A 原数组
     * @param p 数组左侧下标
     * @param r 数组右侧下标
     */
    private static void quickSort(int[] A, int p, int r) {
        if (p < r) {
            int[] range = partition(A, p, r);//执行分区方法，获取等于基准的范围
            quickSort(A, p, range[0] - 1);//对基准左侧的元素再次调用快速排序
            quickSort(A, range[1] + 1, r);//对基准右侧的元素再次调用快速排序
        }
    }

    /**
     * 分区方法-三指针分区法
     * @param A 原数组
     * @param p 左侧数组下标
     * @param r 右侧数组下标
     * @return 完成一轮排序后基准所在的下标(中点)
     */
    private static int[] partition(int[] A, int p, int r) {
        int pivot = A[p];//把第一个元素作为基准
        int sp = p + 1;//左侧指针
        int equal = p + 1;//相等指针
        int bigger = r;//右侧指针
        while (sp <= bigger) {//当左侧指针在右侧指针右边时退出循环
            if (A[sp] < pivot) {//左侧指针扫描到的元素<=基准，左侧指针右移
                swap(A,sp,equal);
                sp++;
                equal++;
            }
            else if (A[sp] == pivot) {//左侧指针扫描到的元素>基准，右侧指针左移一位
                sp++;
            }
            else {
                swap(A, sp, bigger);
                bigger--;
            }
        }
        //以上过程完成之后，equal一定指向第一个等于基准的(并且equal左边全都小于基准)，而bigger一定指向最后一个等于基准的(并且bigger右边全都大于基准)
        //我们要将基准放在中间的一个合适位置，这个位置就是当前equal左边一个的位置
        swap(A, p, equal - 1);
        //上一行已经将基准放在了合适的位置(bigger指向的位置)，返回这个基准所在的位置
        return new int[]{equal,bigger};
    }

    /**
     * 交换数组中两个元素的方法
     */
    private static void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}
